package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         98.1,
		Discription: "矩阵中每个格子对应一个方向移动，初始每个格子都有一个机器人，最终矩阵中剩几个机器人",
		Level:       2,
		Labels: map[string]int{
			"记忆化搜索": 1,
			"中间态":   1,
		},
	})
}

//判断从每个格子出发，是会形成回路，还是会走出矩阵
//用canStay[i][j]做记忆化搜索，0表示待判断，1表示形成回路，-1表示会走出矩阵
//对于每个格子的判断，用map[{i,j}]bool 记录已走过的格子，方便判断回路，递归结束时用defer重置
func LeftRobotNums(grid [][]byte) int {
	m := len(grid)
	n := len(grid[0])
	canStay := make([][]int, m)
	for i := range canStay {
		canStay[i] = make([]int, n)
	}

	//记录从某个格子出发后，走过的格子；dfs返回前用defer恢复状态，不影响下一个格子的判断
	visited := make(map[[2]int]bool, 0)
	var dfs func(int, int) bool
	dfs = func(i, j int) bool {
		defer func() {
			delete(visited, [2]int{i, j})
		}()

		if i < 0 || i >= m || j < 0 || j >= n || canStay[i][j] == -1 {
			return false
		}

		//记忆中能形成回路 or 在递归中形成回路
		if canStay[i][j] == 1 || visited[[2]int{i, j}] {
			return true
		}
		visited[[2]int{i, j}] = true

		switch grid[i][j] {
		case 'L':
			return dfs(i, j-1)

		case 'R':
			return dfs(i, j+1)

		case 'U':
			return dfs(i-1, j)

		case 'D':
			return dfs(i+1, j)
		}

		return false
	}

	//遍历每一个格子，判断从该格子出发是形成回路还是走出矩阵
	res := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if dfs(i, j) {
				canStay[i][j] = 1
				res++
			} else {
				canStay[i][j] = -1
			}
		}
	}

	return res
}
